Abstract

Inference problems play a pivotal role in modern computer science, mathematics and statistics. The guiding question in these problems is to determine the minimum number of queries that enable the inference a latent ground truth, either information-theoretically or algorithmically. Prominent recent success stories include the stochastic block model, compressed sensing, group testing and low-density parity check codes. The techniques employed to tackle these problems originate in information theory, statistical physics, probability theory as well as combinatorics.